The present invention relates to a descriptor based memory queuing system for transmitting data packets to one or more transmit ports in a device of a computer network, and in particular to a system where lost buffers can be detected.
Many computer network devices, such as bridges, routers, switches and/or hubs, receive data packets and must then forward these packets to one or more transmit ports. The determination of which transmit ports a particular packet is to be sent to, is performed by the higher logic of the network device and is already well known to those skilled in the art. The speed at which each transmit port can send out data packets depends on the speed of the connection, the speed of the receiving port and other factors that can change for each port. Also a data packet can be sent to more than one port at a time, in a process known as multicasting, broadcasting and flooding.
Therefore it is important that the status of the individual transmit ports be closely coordinated with the presence of data packets which are to be sent out on those ports. This can be done using transmit queues for each transmit port and copying a pointer or descriptor into the proper transmit queue which points to the address of a buffer in a main data memory which stores the data packet.
A problem in this descriptor queuing scheme is the loss of buffer descriptors. Generally, these problems result from, logic errors in the buffer descriptor management. Lost buffers is potentially a serious problem preventing full utilization of the main memory. In prior art systems, lost buffers can exist in perpetuity or until a full system reset. Also the number of lost buffers tend to increase with time, causing an increasing under utilization of the device and continual degradation of the network.
It is a primary object of the present invention to rapidly detect lost buffers, and prevent network degradation. It is also an objective to then place the buffers back in service without having to restart the entire network device, particularly when queuing is implemented in hardware and can not be easily corrected if there is a fault in the design.
The present invention accomplishes this object by providing a main data memory in the network device. The main data memory includes a plurality of buffers for storing data packets. A plurality of descriptors, or pointers, point to the individual buffers. A descriptor free pool includes a list of the descriptors in the free state.
When the system receives a data packet, it takes one of the descriptors from the descriptor free pool and stores the data packet in the buffer of the main memory as pointed to by that descriptor.
The system, and more particularly a queue control logic, places a copy of the descriptor in one or more of the plurality of transmit queues of which the queue control logic has previously determined the data packet should be sent out on.
The first embodiment of the invention provides two sets of counters to track buffer descriptors. One set of counters tracks the total number of free and active descriptors. The second set of counters tracks the total number of copies of each active descriptor.
When a descriptor is removed from the free pool, the Free Pool Entry Count is decremented. Similarly, when a descriptor is placed back on the Free Pool, the Free Pool Entry Count is incremented.
There is a one for one correspondence between a Reference Memory Location and each buffer/descriptor. Descriptor Reference Memory stores the status of each descriptor and the number of copies of each descriptor.
When a descriptor is placed on one or more transmit queues, the Reference Memory Entry Count is incremented. The descriptor specific Reference Memory location is updated, state is changed from free to active and the copy count indicates the number of transmit queues which have copies of the descriptor. The copy count is also added to the Transmit Queue Elaborated Count and the Reference Memory Elaborated Count.
When a descriptor is removed from a transmit queue, the Transmit Queue Elaborated Count is decremented. When the data associated with the descriptor has been sent to the destination port, the Reference Memory Elaborated Count is decremented as is the descriptor specific count in Reference Memory. When the descriptor specific count decrements to zero, the descriptor state is changed from active to free, the Reference Memory Entry Count is decremented and the descriptor is returned to the Free Pool.
The second embodiment of the invention provides per port descriptor status as well as overall activity status for each buffer descriptor location in Reference Memory. The status of the descriptors is stored in a descriptor reference memory. The status information includes overall status which includes the states of idle, pending, first poll and lost. The status information also includes port status information for each descriptor. Each port status information includes active and free states for each transmit queue. Also provided is a means for the periodic polling of the overall activity state.
When a packet is received, a descriptor is removed from the Free Pool. When the descriptor is placed on one or more of the transmit queues, the overall activity state in the corresponding Reference Memory location moves from Idle to Pending. Each port that received a copy of the descriptor will have its corresponding per port status set to Active.
When a descriptor is removed from a transmit queue, the corresponding per port status is set to Free. If the per port status of all ports is Free, the overall activity state of the descriptor is set to Idle and the descriptor is returned to the Free Pool.
Lost buffers can occur, and can be detected, in several different parts of the network device.
In the first embodiment, it is possible to detect lost buffers by monitoring the descriptor free pool, and the descriptor reference memory. Since all of the descriptors should either be in the descriptor free pool, or should have an active status in the descriptor reference memory, the sum of the number of descriptors in the free pool with the number of descriptors having an active state in the descriptor reference memory should remain constant and equal to the total number of descriptors. A count of the number of descriptors in the descriptor free pool, and of the active descriptors in the descriptor reference memory is maintained and periodically checked. If the total of these two numbers does not equal the total number of descriptors, an error is indicated.
A transmit queue elaborated counter and a reference memory elaborated counter are also provided to maintain separate accounting of the descriptors in the transmit queues. When a descriptor is placed in one or more transmit queues, both the transmit queue elaborated counter and the reference memory elaborated counter are incremented by the number of queues to which the descriptor is added. When a descriptor is removed from one of the transmit queues, the transmit queue elaborated counter is decremented. When the data packet corresponding to the removed descriptor is transmitted by the port, the reference memory elaborated counter is decremented. Because of the time difference in decrementing the transmit queue elaborated counter and the reference memory elaborated counter, the value of these counters will be different until all of the data packets for the removed descriptors have been transmitted. However at no time, should the difference between the counters be greater than the number of ports. This is because each port should only be holding one data packet before the reference memory elaborated counter is decremented. If the difference between the values of the two counters is greater than the number of ports, a lost buffer is indicated.
When a lost buffer is indicated, the overall healing system can be reinitialized. This involves clearing memory, and resetting counters, which is known to the person of ordinary skill in the art and is therefore not described further in this specification.
As an alternative to initializing the entire queue system, just the main memory, the plurality of transmit queues, the descriptor reference memory, the count and the descriptor free pool can be initialized when the total of the number of descriptors in the free pool plus the number of descriptors having the active state does not equal the total number of descriptors. If the lost buffer is indicated due to a discrepancy between the transmit queue elaborated counter and the reference memory elaborated counter, these counters can also be reinitialized.
In a second embodiment, a more elaborate detection of lost buffers is provided. The descriptor reference memory includes two different types of information for each descriptor. One type of information, is the overall status of the descriptor. This overall status has the states of idle, pending, first poll, and lost. The second type of information is port status information. Each descriptor specific entry in reference memory keeps track of which transmit queues have a copy of the descriptor has been placed onto. The port status information for each descriptor therefore has a separate marker for each of the transmit queues, and this marker can indicate a free or an active state. If a copy of the descriptor is on a particular transmit queue, the marker for that transmit queue will have the active state. Correspondingly if a transmit queue does not have a copy of the descriptor, the marker for that transmit queue in that descriptor status information will be in the free state.
When a copy of the descriptor is placed in one or more transmit queues, the corresponding markers in the descriptor reference memory are set to the active state, and the overall status for that descriptor is set to the pending state.
Every time a copy of a descriptor is removed from a transmit queue, the corresponding marker in the status information for that descriptor is set to the free state. The remaining markers in that descriptor status information are checked to see if any other markers are in the active state. If other markers are in the active state, then the overall status is set to, or remains at, the pending state. If no other markers for that descriptor are on the active state, the overall status for that descriptor is set to idle.
This checking determines whether or not other copies of the descriptor are in other transmit queues, after a copy has been removed from one transmit queue. In order to accomplish this checking, the individual queues could be directly checked instead of checking the markers for a particular descriptor.
The overall status information of the descriptors, as maintained in the reference memory, is polled repetitively. If the overall status information of a descriptor is found to be pending during a polling operation, the overall status information for that descriptor is then set to the first poll state. If during the polling process, an overall status is found to be in the first poll state, the overall status is then set to the lost state. The removing of descriptors from the transmit queues occurs repetitively, and is interspaced with the polling. If the removal of a descriptor occurs, and the overall status is in either the first poll or lost state, the overall status is set to pending. Note that allowing the overall state to move from Lost to Pending allows for the return of descriptors that have been incorrectly marked as Lost.
When descriptors have an overall status of the lost state, corrective action can occur. In the second embodiment, the corrective action occurs when the number of descriptors having an overall status of lost is above a predetermined threshold value.
When the number of descriptors in the lost state is above this threshold value, the port status of these descriptors are checked, and the transmit queues that correspond to the markers in the active state are also checked. If the transmit queues do not contain the lost descriptor, the descriptor can be recovered by initializing the descriptor reference memory for that descriptor and adding that descriptor to the descriptor free pool. If the descriptor is found on the transmit queue, the descriptor can be left on the transmit queue, to be eventually transmitted. The overall status can be changed back to pending, or the overall status can remain in the lost state with the checking reoccurring every time the threshold is exceeded.
The various features of novelty which characterize the invention are pointed out with particularity in the claims annexed to and forming a part of this disclosure. For a better understanding of the invention, its operating advantages and specific objects attained by its uses, reference is made to the accompanying drawings and descriptive matter in which preferred embodiments of the invention are illustrated.